class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution01 {
	private int pathNum;

    public int pathSum(TreeNode root, int targetSum) {
		if(root == null){
			return pathNum;
		}
		// 递归：每一个节点都作为一个根节点
		dfs(root, targetSum, 0);
		// 递归：只是单纯的向下走一步，更新dfs的当前根节点
		pathSum(root.left, targetSum);
		pathSum(root.right, targetSum);
		return pathNum;
    }

	public void dfs(TreeNode curNode, int targetSum, int curSum){
		if(curNode == null){
			return;
		}
		// 每向下遍历一层，累加当前根节点到当前节点的和
		curSum += curNode.val;
		if(curSum == targetSum){
			pathNum++;
			// 一个节点在其子树上可能存在多条
			// return;
		}
		dfs(curNode.left, targetSum, curSum);
		dfs(curNode.right, targetSum, curSum);
	}
}
